﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Hard_37_SolveSudoku
{
    class MainProject
    {
        static void Main(string[] args)
        {
            char[][] array = new char[][]
            {
                new char[]{ '.', '.', '9', '7', '4', '8', '.', '.', '.' },
                new char[]{ '7', '.', '.', '.', '.', '.', '.', '.', '.' },
                new char[]{ '.', '2', '.', '1', '.', '9', '.', '.', '.' },
                new char[]{ '.', '.', '7', '.', '.', '.', '2', '4', '.' },
                new char[]{ '.', '6', '4', '.', '1', '.', '5', '9', '.' },
                new char[]{ '.', '9', '8', '.', '.', '.', '3', '.', '.' },
                new char[]{ '.', '.', '.', '8', '.', '3', '.', '2', '.' },
                new char[]{ '.', '.', '.', '.', '.', '.', '.', '.', '6' },
                new char[]{ '.', '.', '.', '2', '7', '5', '9', '.', '.' },
            };
            SolveSudoku(array);

            foreach (var arr in array)
            {
                foreach (var item in arr)
                {
                    Console.Write(item + "-");
                }
                Console.WriteLine("--------------------");
            }
            //Console.WriteLine(IsPalindrome(1000021));
            Console.ReadKey();
        }

        #region 回溯法
        public static void SolveSudoku(char[][] board)
        {
            bool[,] row = new bool[9, 10];
            bool[,] col = new bool[9, 10];
            bool[,,] _3x3 = new bool[3, 3, 10];

            for (int i = 0; i < board.Length; i++)
            {
                for (int j = 0; j < board[i].Length; j++)
                {
                    if (board[i][j] >= 49 && board[i][j] <= 57)
                    {
                        int num = board[i][j] - '0';
                        row[i, num] = true;
                        col[j, num] = true;
                        _3x3[i / 3, j / 3, num] = true;
                    }
                }
            }
            RecusiveSolveSudoku(board, row, col, _3x3, 0, 0);
        }

        private static bool RecusiveSolveSudoku(char[][] board, bool[,] rows, bool[,] cols, bool[,,] _3x3, int row, int col)
        {
            if (col == board[row].Length)
            {
                row++;
                col = 0;
                if (row == board.Length) return true;
            }

            if (board[row][col] == '.')
            {
                for (int i = 1; i <= 9; i++)
                {
                    if (!(rows[row, i] || cols[col, i] || _3x3[row / 3, col / 3, i]))
                    {
                        rows[row, i] = true;
                        cols[col, i] = true;
                        _3x3[row / 3, col / 3, i] = true;

                        board[row][col] = char.Parse(i.ToString());

                        if (RecusiveSolveSudoku(board, rows, cols, _3x3, row, col + 1))
                        {
                            return true;
                        }
                        board[row][col] = '.';
                        rows[row, i] = false;
                        cols[col, i] = false;
                        _3x3[row / 3, col / 3, i] = false;
                    }
                }
            }
            else
            {
                return RecusiveSolveSudoku(board, rows, cols, _3x3, row, col + 1);
            }
            return false;
        }
        #endregion

        #region 自己尝试解决

        public class Sudoku
        {
            public int xy;
            public List<char> chars;

            public Sudoku(Sudoku item)
            {
                this.xy = item.xy;
                chars = new List<char>();
                foreach (var val in item.chars)
                {
                    chars.Add(val);
                }
            }

            public Sudoku(int val, List<char> list)
            {
                this.xy = val;
                this.chars = list;
            }
        }

        public static void SolveSudoku1(char[][] board)
        {
            //思路：遍历所有的未填，多解的暂时存储，先结束唯一解的，然后重复上一步（未完待续，搞明白题解）

            //Dictionary<int, List<char>> dic = new Dictionary<int, List<char>>();
            Queue<Sudoku> dic = new Queue<Sudoku>();
            for (int i = 0; i < board.Length; i++)
            {
                for (int j = 0; j < board[i].Length; j++)
                {
                    if (board[i][j] == '.')
                    {
                        List<char> list = GetAllSolution(board, i, j);
                        if (list.Count == 1)
                        {
                            board[i][j] = list[0];
                        }
                        else if (list.Count == 0)
                        {
                            Console.WriteLine("Error1");
                        }
                        else
                        {
                            dic.Enqueue(new Sudoku(Encryption(i, j), list));
                        }
                    }
                }
            }
            Console.WriteLine("-----------------------------");

            foreach (var arr in board)
            {
                foreach (var item in arr)
                {
                    Console.Write(item + "-");
                }
                Console.WriteLine("--------------------");
            }

            bool isOne = false;
            bool isRecord = false;
            Queue<Sudoku> record = new Queue<Sudoku>();
            List<char> recordList = new List<char>();
            Sudoku recordSu = null;
            while (dic.Count > 0)
            {
                if (dic.Count == 34)
                {
                    foreach (var arr in board)
                    {
                        foreach (var item in arr)
                        {
                            Console.Write(item + "-");
                        }
                        Console.WriteLine("--------------------");
                    }
                }
                isOne = false;
                Sudoku sudoku1 = dic.Peek();
                int size = dic.Count;
                for (int i = 0; i < size; i++)
                {
                    Sudoku sudoku = dic.Dequeue();
                    int x = sudoku.xy / 100;
                    int y = sudoku.xy % 100;
                    List<char> list = GetAllSolution(board, x, y);
                    if (list.Count == 1)
                    {
                        board[x][y] = list[0];
                        isOne = true;
                    }
                    else if (list.Count == 0)
                    {
                        Console.WriteLine("Error2");
                    }
                    else
                    {
                        if (list.Count < sudoku1.chars.Count) sudoku1 = sudoku;
                        dic.Enqueue(sudoku);
                    }
                }
                if (!isOne)
                {
                    if (!isRecord)
                    {
                        foreach (var item in dic) record.Enqueue(new Sudoku(item));
                        recordSu = sudoku1;
                    }
                    else
                    {
                        dic.Clear();
                        foreach (var item in record) dic.Enqueue(new Sudoku(item));
                    }
                    int x = recordSu.xy / 100;
                    int y = recordSu.xy % 100;
                    for (int i = 0; i < sudoku1.chars.Count; i++)
                    {
                        if (!recordList.Contains(sudoku1.chars[i]))
                        {
                            recordList.Add(sudoku1.chars[i]);
                            board[x][y] = sudoku1.chars[i];
                        }
                    }
                }
            }
        }

        public static int Encryption(int x, int y)
        {
            return x * 100 + y;
        }

        public static List<char> GetAllSolution(char[][] board, int x, int y)
        {
            List<char> list = new List<char>() { '1', '2', '3', '4', '5', '6', '7', '8', '9' };
            for (int i = 0; i < 9; i++)
            {
                if (list.Contains(board[x][i])) list.Remove(board[x][i]);
                if (list.Contains(board[i][y])) list.Remove(board[i][y]);
            }
            int blockX = x / 3;
            int blockY = y / 3;

            for (int i = (blockX * 3); i < (blockX * 3) + 3; i++)
            {
                for (int j = (blockY * 3); j < (blockY * 3) + 3; j++)
                {
                    if (list.Contains(board[i][j])) list.Remove(board[i][j]);
                }
            }

            Console.Write("{0}/{1}  ", x, y);
            foreach (var item in list)
            {
                Console.Write("{0}   ", item);
            }
            Console.WriteLine();
            return list;
        }
        #endregion
    }
}
